using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0120. 三角形最小路径和")]
    public class No0120_MinimumTotal : AbsBaseTestItem
    {
        /*
        给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
        相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
        */
        public override void OnTest()
        {
            Assert.TestExe(MinimumTotal,
                new List<IList<int>>()
                {
                    new int[]    {2},
                    new int[]   {3,4},
                    new int[]  {6,5,7},
                    new int[] {4,1,8,3},
                },
                11);

            Assert.TestExe(MinimumTotal2,
                new List<IList<int>>()
                {
                    new int[]    {2},
                    new int[]   {3,4},
                    new int[]  {6,5,7},
                    new int[] {4,1,8,3},
                },
                11);
        }

        /// <summary>
        ///  方法一：动态规划
        /// </summary>
        public int MinimumTotal(IList<IList<int>> triangle)
        {
            int n = triangle.Count;
            int[,] f = new int[n, n];
            f[0, 0] = triangle[0][0];
            for (int i = 1; i < n; i++)
            {
                f[i, 0] = f[i - 1, 0] + triangle[i][0];
                for (int j = 1; j < i; j++)
                {
                    f[i, j] = Math.Min(f[i - 1, j - 1], f[i - 1, j]) + triangle[i][j];
                }
                f[i, i] = f[i - 1, i - 1] + triangle[i][i];
            }
            int minTotal = f[n - 1, 0];
            for (int i = 1; i < n; i++)
            {
                minTotal = Math.Min(minTotal, f[n - 1, i]);
            }
            return minTotal;
        }

        /// <summary>
        ///  方法二：动态规划 + 空间优化
        /// </summary>
        public int MinimumTotal2(IList<IList<int>> triangle)
        {
            int n = triangle.Count;
            int[] f = new int[n];
            f[0] = triangle[0][0];
            for (int i = 1; i < n; i++)
            {
                f[i] = f[i - 1] + triangle[i][i];
                for (int j = i - 1; j > 0; j--)
                {
                    f[j] = Math.Min(f[j - 1], f[j]) + triangle[i][j];
                }
                f[0] += triangle[i][0];
            }
            int minTotal = f[0];
            for (int i = 1; i < n; i++)
            {
                minTotal = Math.Min(minTotal, f[i]);
            }
            return minTotal;
        }
    }
}
